package main.java.exercise;

import main.java.framework.StudentInformation;
import main.java.framework.StudentSolution;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;

public class StudentSolutionImplementation implements StudentSolution {
    @Override
    public StudentInformation provideStudentInformation() {
        return new StudentInformation(
                "", // Vorname
                "", // Nachname
                "" // Matrikelnummer
        );
    }

    /*
     * used for internal tree representation, greatly increasing readability
     */
    private class BinaryTree {
        int payload;
        BinaryTree left;
        BinaryTree right;

        // constructor
        BinaryTree(int payload) {
            this.payload = payload;
        }
    }

    /**
     * checks if an array has elements to iterate still
     * @param array array to check
     * @param i current index
     * @return boolean representing whether elements to iterate exist
     */
    private boolean emptied(int[] array, int i) {
        return !(i < array.length);
    }

    /**
     * computes correct left index for a flattened tree
     * @param i parent index
     * @return resulting index
     */
    private int left(int i) {
        return (2 * i) + 1;
    }

    /**
     * computes correct right index for a flattened tree
     * @param i parent index
     * @return resulting index
     */
    private int right(int i) {
        return  (2 * i) + 2;
    }

    /**
     * increments an atomic integer, method exists for readability
     * @param integer atomic integer to increment
     */
    private void inc(AtomicInteger integer) {
        integer.set(integer.get() + 1);
    }

    private void dec(AtomicInteger integer) {
        integer.set(integer.get() - 1);
    }

    private BinaryTree rebuildInPreWithPendingNode(int[] inOrderTraversal, AtomicInteger in, int[] preOrderTraversal, AtomicInteger pre, int pending) {
        if (emptied(preOrderTraversal, pre.get())) return null;

        BinaryTree root = new BinaryTree(preOrderTraversal[pre.get()]);
        inc(pre);

        if (root.payload == inOrderTraversal[in.get()]) root.left = null;
        else root.left = rebuildInPreWithPendingNode(inOrderTraversal, in, preOrderTraversal, pre, root.payload);
        inc(in);

        if (inOrderTraversal[in.get()] == pending) root.right = null;
        else root.right = rebuildInPreWithPendingNode(inOrderTraversal, in, preOrderTraversal, pre, pending);

        return root;
    }

    // implementation of
    // https://www.sciencedirect.com/science/article/pii/0893965989901225
    private BinaryTree rebuildInPreTreeRecursive(int[] inOrderTraversal, AtomicInteger in, int[] preOrderTraversal, AtomicInteger pre) {
        if (emptied(preOrderTraversal, pre.get())) return null;

        BinaryTree root = new BinaryTree(preOrderTraversal[pre.get()]);
        inc(pre);

        if (root.payload == inOrderTraversal[in.get()]) root.left = null;
        else root.left = rebuildInPreWithPendingNode(inOrderTraversal, in, preOrderTraversal, pre, root.payload);
        inc(in);

        if (emptied(inOrderTraversal, in.get())) root.right = null;
        else root.right = rebuildInPreTreeRecursive(inOrderTraversal, in, preOrderTraversal, pre);

        return root;
    }

    private BinaryTree rebuildInPreTree(int[] inOrderTraversal, int[] preOrderTraversal, AtomicInteger pre, int inS, int inE) {
        if (inS > inE || inS >= inOrderTraversal.length || pre.get() >= preOrderTraversal.length) return null;

        BinaryTree root = new BinaryTree(preOrderTraversal[pre.get()]);
        inc(pre);

        int inOrderIndex = -1;
        for (int i = inS; i <= inE; i++) {
            if (root.payload == inOrderTraversal[i]) {
                inOrderIndex = i;
                break;
            }
        }

        root.left = rebuildInPreTree(
                inOrderTraversal,
                preOrderTraversal,
                pre,
                inS,
                inOrderIndex - 1
        );

        root.right = rebuildInPreTree(
                inOrderTraversal,
                preOrderTraversal,
                pre,
                inOrderIndex + 1,
                inE
        );

        return root;
    }

    private BinaryTree rebuildInPostTree(int[] inOrderTraversal, int[] postOrderTraversal, AtomicInteger post, int inS, int inE) {
        if (inS > inE || inS >= inOrderTraversal.length || post.get() < 0) return null;

        BinaryTree root = new BinaryTree(postOrderTraversal[post.get()]);
        dec(post);

        int inOrderIndex = -1;
        for (int i = inS; i <= inE; i++) {
            if (root.payload == inOrderTraversal[i]) {
                inOrderIndex = i;
                break;
            }
        }

        root.right = rebuildInPostTree(
                inOrderTraversal,
                postOrderTraversal,
                post,
                inOrderIndex + 1,
                inE
        );

        root.left = rebuildInPostTree(
                inOrderTraversal,
                postOrderTraversal,
                post,
                inS,
                inOrderIndex - 1
        );

        return root;
    }

    /**
     * takes a BinaryTree and flattens it into an int[] array, in accordance
     * with task specifications
     * @param reconstructedTree array to fill with the flattened tree
     * @param root node of the tree to flatten
     * @param k index of the supplied node
     */
    private void flatten(int[] reconstructedTree, BinaryTree root, int k) {
        if (root == null) return;
        reconstructedTree[k] = root.payload;
        flatten(reconstructedTree, root.left, left(k));
        flatten(reconstructedTree, root.right, right(k));
    }

    public void reconstructFromInAndPreOrder(int[] inOrderTraversal, int[] preOrderTraversal, int[] reconstructedTree) {
        assert inOrderTraversal.length == preOrderTraversal.length;
        BinaryTree root = rebuildInPreTree(inOrderTraversal, preOrderTraversal,
                new AtomicInteger(0), 0, inOrderTraversal.length - 1);
        //BinaryTree root = rebuildInPreTreeRecursive(inOrderTraversal, new AtomicInteger(0), preOrderTraversal, new AtomicInteger(0));
        flatten(reconstructedTree, root, 0);
    }

    public void reconstructFromInAndPostOrder(int[] inOrderTraversal, int[] postOrderTraversal, int[] reconstructedTree) {
        assert inOrderTraversal.length == postOrderTraversal.length;
        BinaryTree root = rebuildInPostTree(inOrderTraversal, postOrderTraversal,
                new AtomicInteger(postOrderTraversal.length - 1), 0, inOrderTraversal.length - 1);
        flatten(reconstructedTree, root, 0);
    }
}
